package 左哥算法.ch10暴力递归;

import org.junit.Test;

public class 存在枚举的动态规划 {
    /**
     * 你一个数组coins，数组中放着某个面值的硬币。（硬币面值不会重复，每种面额可重复使用）
     * 计算金额为amount时，有多少种方式凑成该金额
     * 思路：
     * 设面额分别为a1，a2,...an。
     * 凑成amount的方式有：
     * 选0张a1剩下的钱选a2到an，选1张a1剩下的钱选a2到an。
     * 选择的个数为：n；选择的限制为：an*数量<=剩下的钱
     */
    public int fun(int[] coins, int index, int rest) {
        if (rest == 0) {
            return 1;
        }
        if (rest < 0 || index == coins.length) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i * coins[index] <= rest; i++) {  //单个选择的范围
            res += fun(coins, index + 1, rest - coins[index] * i);
        }
        return res;
//        return fun(coins,index,rest-coins[index])+fun(coins,index+1,rest);    //可以优化成这样
    }

    /**
     * 转动态规划,版本1
     */
    public int dpFun1(int[] coins, int amount) {
        int[][] dp = new int[coins.length + 1][amount + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        for (int index = coins.length - 1; index >= 0; index--) {
            for (int j = 1; j <= amount; j++) {
                for (int i = 0; i*coins[index] <= j; i++) {
                    dp[index][j]+=dp[index+1][j-coins[index]*i];
                }
            }
        }
        return dp[0][amount];
    }

    /**
     * 经过打表我们发现待求位置的依赖与他上一个偏移量的依赖除最后一个，其他完全相同
     * 所以我们可以直接使用上一层的偏移量加上最后一个依赖求出该位置的值
     * dp[i][j]=dp[i][j-偏移量]+dp[i+1][j]
     */
    public int dpFun2(int[] coins, int amount){
        int[][] dp = new int[coins.length + 1][amount + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        for (int index = coins.length - 1; index >= 0; index--) {
            for (int j = 1; j <= amount; j++) {
                dp[index][j]=j>=coins[index]?dp[index][j-coins[index]]:0;
                dp[index][j]+=dp[index+1][j];
            }
        }
        return dp[0][amount];
    }

    @Test
    public void test() {
        int[] coins = {2, 3, 5, 7};
        int amount = 10;
        System.out.println(fun(coins, 0, amount));
        System.out.println(dpFun1(coins, amount));
        compare();
    }

    public void compare(){
        int count=1000;
        while (count-- > 0) {
            int[] coins=new int[(int) (Math.random()*20+1)];
            int amount= (int) (Math.random()*60+1);
            for (int i = 0; i < coins.length; i++) {
                coins[i]= (int) (Math.random()*30+1);
            }
//            int fun = fun(coins, 0, amount);
            int fun = dpFun2(coins,  amount);
            int dpFun = dpFun1(coins, amount);
            if (fun!=dpFun){
                System.out.println("存在错误");
            }
        }
    }
}
